표준 끝말잇기

유향 그래프 모델

끝말잇기의 구조적 분석: 유향 그래프 모델

끝말잇기 게임의 규칙과 진행 과정은 유향 그래프(Directed Graph) 모델을 통해 수학적으로 명확하게 정의할 수 있습니다. 이 모델을 사용하면 게임의 모든 상태와 규칙을 정점과 엣지의 관계로 환원하여 분석하는 것이 가능해집니다.

게임 요소와 그래프 요소의 대응

끝말잇기를 구성하는 두 가지 핵심 요소인 '글자'와 '단어'는 각각 그래프의 '정점'과 '엣지'에 직접 대응됩니다.

정점 (Vertex): 개별 문자
게임에서 사용되는 '가', '나', '다'와 같은 모든 개별 문자(음절)는 유향 그래프의 정점(Vertex 또는 Node)에 해당합니다.
유향 엣지 (Directed Edge): 단어
하나의 단어는 두 정점을 잇는 유향 엣지(Directed Edge)로 정의됩니다. 이때 단어의 첫 문자는 엣지의 시작 정점(start vertex)이 되고, 끝 문자는 끝 정점(end vertex)이 됩니다. 예를 들어, "언어"라는 단어는 '언' 정점에서 '어' 정점으로 향하는 유향 엣지입니다.

게임 플레이는 한 정점에서 시작하여 엣지를 통해 다른 정점으로 이동하는 과정의 연속입니다. 한 플레이어가 특정 엣지를 통해 어떤 정점에 도달하면, 다음 플레이어는 반드시 해당 정점에서 시작하는 다른 엣지를 선택해야 합니다.

게임의 상태와 행동의 정형화

그래프 모델을 통해 게임의 특정 시점과 플레이어의 행동을 다음과 같이 엄밀하게 정의할 수 있습니다.

포지션 (Position): 현재 게임 상태
게임의 특정 순간의 상태, 즉 포지션은 순서쌍 $(G,v)$ 로 표현됩니다.
- $G$ (Graph): 아직 사용되지 않은 단어들의 집합, 즉 현재 사용 가능한 엣지들로 구성된 그래프입니다.
- $v$ (Vertex): 현재 단어를 시작해야 하는 문자에 해당하는 정점입니다.
수 (Move): 상태 전이
플레이어가 단어를 선택하는 '수'는 그래프의 상태를 전이시키는 행위입니다. 포지션 $(G, v)$ 에 있는 플레이어는 정점 $v$ 에서 나가는(outgoing) 엣지 $e$ 를 하나 선택합니다. 이 행동의 결과로, 엣지 $e$ 는 그래프 $G$ 에서 제거되며, 다음 플레이어는 새로운 포지션 $(G-e, end(e))$ 를 맞이하게 됩니다. 여기서 $end(e)$ 는 엣지 $e$ 의 끝 정점을 의미합니다.

게임의 종료 조건

게임의 패배 조건은 그래프 상에서 명확하게 정의됩니다. 플레이어의 차례가 되어 포지션 $(G,v)$ 를 받았을 때, 만약 현재 그래프 $G$ 에 정점 $v$ 에서 시작하는 엣지가 하나도 없다면, 해당 플레이어는 유효한 '수'를 둘 수 없습니다. 이 경우 플레이어는 패배하고 게임은 종료됩니다. 이는 정점 v의 나가는 차수(out-degree)가 0인 상황과 같습니다.